package com.lwt.codetop.backtracking;
// 46. 全排列

import java.util.ArrayList;
import java.util.List;

/**
 * 思路：全排列型dfs模板
 */
public class Permutations {
    private static int n;
    private static int N = 20;
    private static boolean[] st = new boolean[N];
    private static List<List<Integer>> res = new ArrayList<>();
    private static List<Integer> path = new ArrayList<>();
    public static void main(String[] args) {
        // 构建测试用例
        int[] nums = {1, 2, 3};
        n = nums.length;
        dfs(0, nums);
        System.out.println(res);
    }

    /**
     * 全排列型dfs模板
     * @param u
     * @return
     */
    private static void dfs(int u, int[] nums) {
        // 递归出口
        if(u == n){
            res.add(new ArrayList<>(path)); // 注意要new 新的
            return ;
        }
        for (int i = 0; i < n; i++) {
            if(st[i] == false){
                st[i] = true;
                path.add(nums[i]);
                dfs(u + 1, nums);
                st[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }
}
